翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Bandwidth problem ： ウィキペディア英語版 Graph bandwidth In graph theory, the graph bandwidth problem is to label the ''n'' vertices ''vi'' of a graph ''G'' with distinct integers ''f''(''vi'') so that the quantity $\backslash max\backslash$ is minimized (''E'' is the edge set of ''G''). The problem may be visualized as placing the vertices of a graph at distinct integer points along the ''x''-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.〔 The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights ''wij'' and the cost function to be minimized is $\backslash max\backslash$. In terms of matrices, the (unweighted) graph bandwidth is the bandwidth of the symmetric matrix which is the adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size . ==Bandwidth formulas for some graphs== For several families of graphs, the bandwidth $\backslash varphi(G)$ is given by an explicit formula. The bandwidth of a path graph ''P''''n'' on ''n'' vertices is 1, and for a complete graph ''K''''m'' we have $\backslash varphi(K\_n)=n-1$. For the complete bipartite graph ''K''''m'',''n'', :$\backslash varphi(K\_)\; =\; \backslash lfloor\; (m-1)/2\backslash rfloor+n$, assuming $m\; \backslash ge\; n\backslash ge\; 1,$ which was proved by Chvátal.〔A remark on a problem of Harary. V. Chvátal, ''Czechoslovak Mathematical Journal'' 20(1):109–111, 1970. (http://dml.cz/dmlcz/100949 )〕 As a special case of this formula, the star graph $S\_k\; =\; K\_$ on ''k'' + 1 vertices has bandwidth $\backslash varphi(S\_)\; =\; \backslash lfloor\; (k-1)/2\backslash rfloor+1$. For the hypercube graph $Q\_n$ on $2^n$ vertices the bandwidth was determined by to be :$\backslash varphi(Q\_n)=\backslash sum\_^\; \backslash binom.$ Chvatálová showed〔Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' 11, 249–253, 1975.〕 that the bandwidth of the ''m'' × ''n'' square grid graph $P\_m\; \backslash times\; P\_n$, that is, the Cartesian product of two path graphs on $m$ and $n$ vertices, is equal to min. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph bandwidth」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.